function solveNQueens(n: number): string[][] {
    const results:string[][] = [];
    backtrack(results,n);
    return results;
};
function backtrack(results:string[][],n:number,queensColumns:number[] =[],row:number=0) {
    if(row === n){
        results.push(queensColumns.map(col=> '.'.repeat(col) + 'Q'+'.'.repeat(n-col-1)));
        return;
    }
    for(let col = 0; col<n; col++){
        if(![...queensColumns].some((qCol, qRow)=> qCol===col || Math.abs(qCol - col ) ===  row -qRow)){
            backtrack(results,n,[...queensColumns,col],row+1);
        }
    }
}